home *** CD-ROM | disk | FTP | other *** search
Text File | 1996-04-25 | 49.9 KB | 1,528 lines | [TEXT/CWIE] |
- //================================================================================
- // Greg Anderson
- // db+
- //
- // Cursor to an database record
- // 16 May 1994
- // 31 Dec 1994
- //
- // Every database record is an entry in a balanced binary tree. The
- // exact type of tree used is an AVL tree (named after it inventors,
- // G.M. Adelson-Velskii and E.M. Landis), as described in
- // _Data Structures & Program Design_, (2nd edition) by R.L. Kruse,
- // pp. 344-356.
- //================================================================================
-
- #include "DBRecord.h"
-
- #include "Transaction.h"
-
- #include "Exceptions.h"
-
- #define INHERITED TAbstractRecord
-
- //--------------------------------------------------------------------------------
- // TDBRecord::~TDBRecord
- //--------------------------------------------------------------------------------
- TDBRecord::~TDBRecord()
- {
- } // TDBRecord::~TDBRecord
-
- //--------------------------------------------------------------------------------
- // TDBRecord::CompareTreeOrder
- //--------------------------------------------------------------------------------
- CompareEnumeration TDBRecord::CompareTreeOrder(TTransaction* t, AConst<TDBRecord> secondObject) const
- {
- CompareEnumeration theOrder = this->CompareSortKeys(t, secondObject);
- if(theOrder == kObjectKeysEqual)
- theOrder = this->DetermineCompareEnumeration(this->RecordIndex(), secondObject->RecordIndex());
- return theOrder;
- } // TDBRecord::CompareTreeOrder
-
- //--------------------------------------------------------------------------------
- // TDBRecord::FreeOwnedData
- //--------------------------------------------------------------------------------
- void TDBRecord::FreeOwnedData(TTransaction* t)
- {
- //
- // If this entry contains any sub-elements, make them all free
- // (they will in turn free all of their sub-elements)
- //
- if(this->RecordCanHaveElements(t))
- {
- AConst<TDBRecord> elements = this->TopElementRecord(t);
- if(elements.Exists())
- (this->Transaction()->GetDBRecordUpdatePointer(elements))->FreeEntireTree(t);
- }
-
- //
- // If this entry contains any properties, make them all free
- // (they will in turn free all of their referenced data)
- //
- if(this->RecordCanHaveProperties(t))
- {
- AConst<TDBRecord> properties = this->TopPropertyRecord(t);
- if(properties.Exists())
- (this->Transaction()->GetDBRecordUpdatePointer(properties))->FreeEntireTree(t);
- }
-
- INHERITED::FreeOwnedData(t);
- } // TDBRecord::FreeOwnedData
-
- //--------------------------------------------------------------------------------
- // TDBRecord::FreeThisRecord
- //--------------------------------------------------------------------------------
- void TDBRecord::FreeThisRecord(TTransaction* t)
- {
- //
- // If this record is part of a tree, then remove it
- //
- if(this->RecordIsInATree(t))
- this->RemoveFromTree(t);
-
- INHERITED::FreeThisRecord(t);
- } // TDBRecord::FreeThisRecord
-
- //--------------------------------------------------------------------------------
- // TDBRecord::FreeEntireTree
- //
- // This is a DANGEROUS routine; it frees this record and all of its siblings!
- // Usually, you won't want to call it directly; see
- // TDBRecord::FreeThisRecord.
- //
- // NOTE: No effort is made to remove any existing references to this tree;
- // it is assumed that the caller will do that before deleting the tree.
- //--------------------------------------------------------------------------------
- void TDBRecord::FreeEntireTree(TTransaction* t)
- {
- //
- // We could just use an iterator, but it would be inefficient to
- // call RemoveCurrent on every node when we are just trying to
- // delete everything anyway.
- //
- AConst<TDBRecord> current = this->FirstItemInSubTree(t);
- while(current.Exists())
- {
- AConst<TDBRecord> next;
-
- //
- // If 'current' has children, then go down
- // to the last child in the tree and do nothing
- // else this iteration
- //
- if(current->HasLeftSibling(t))
- next = current->FirstItemInSubTree(t);
- else if(current->HasRightSibling(t))
- next = current->LastItemInSubTree(t);
- //
- // If 'current' has no children, then free it
- //
- else
- {
- //
- // The first thing to do is to go up to the
- // parent and remove the link that points to
- // the record we are deleting. Once the node
- // to be deleted has been snipped from the tree,
- // we delete it.
- //
- next = current->ParentSibling(t);
- if(next.Exists())
- {
- ChildIdentifier whichChild = next->IdentifyChild(t, current);
- (this->Transaction()->GetDBRecordUpdatePointer(next))->SetChildLinkOfNewParent(t, AConst<TDBRecord>(nil), whichChild);
- }
- //
- // Set the parent sibling of the current node to 'nil'
- // so that it will not be removed from the tree when
- // we call 'FreeThisRecord' (since we just removed
- // it manually).
- //
- (this->Transaction()->GetDBRecordUpdatePointer(current))->SetParentSibling(t, nil);
- (this->Transaction()->GetDBRecordUpdatePointer(current))->FreeThisRecord(t);
- }
-
- //
- // We're done with the current node (for now... if it had
- // children, we'll come back to it later); go on to the 'next' node.
- //
- current = next;
- }
- } // TDBRecord::FreeEntireTree
-
- //--------------------------------------------------------------------------------
- // TDBRecord::IdentifyChild
- //
- // Determine how 'testChild' is linked to this record, or return
- // 'kNodeIsNotAChild' if it is not.
- //--------------------------------------------------------------------------------
- ChildIdentifier TDBRecord::IdentifyChild(TTransaction* t, AConst<TDBRecord> testChild) const
- {
- Require(testChild.Exists());
-
- ChildIdentifier childID = kNodeIsNotAChild;
- long testChildIndex = testChild->RecordIndex();
-
- //
- // Find a link that points to the testChild
- //
- if(this->LeftSiblingIndex(t) == testChildIndex)
- childID = kNodeIsLeftChild;
- else if(this->RightSiblingIndex(t) == testChildIndex)
- childID = kNodeIsRightChild;
- else if(this->RecordCanHaveElements(t) && (this->TopChildIndex(t) == testChildIndex))
- childID = kNodeIsTopOfElementTree;
- else if(this->RecordCanHaveProperties(t) && (this->TopPropertyIndex(t) == testChildIndex))
- childID = kNodeIsTopOfPropertyTree;
-
- //
- // Make sure that the 'testChild' is marked as being
- // at the top of the tree if it is in a 'top of tree'
- // pointer, and make sure that it is not marked as being
- // at the top of the tree if it is not.
- //
- if((childID == kNodeIsLeftChild) || (childID == kNodeIsRightChild))
- Require(testChild->RecordIsAtTopOfTree(t) == false);
- if((childID == kNodeIsTopOfElementTree) || (childID == kNodeIsTopOfPropertyTree))
- Require(testChild->RecordIsAtTopOfTree(t) == true);
-
- return childID;
- } // TDBRecord::IdentifyChild
-
- //--------------------------------------------------------------------------------
- // TDBRecord::DeepestSubtree
- //
- // Debugging function only
- //--------------------------------------------------------------------------------
- long TDBRecord::DeepestSubtree(TTransaction* t) const
- {
- long leftDepth = 0;
- AConst<TDBRecord> left = this->LeftSibling(t);
- if(left.Exists())
- {
- leftDepth = 1 + left->DeepestSubtree(t);
- }
- long rightDepth = 0;
- AConst<TDBRecord> right = this->RightSibling(t);
- if(right.Exists())
- {
- rightDepth = 1 + right->DeepestSubtree(t);
- }
-
- return rightDepth > leftDepth ? rightDepth : leftDepth;
- } // TDBRecord::DeepestSubtree
-
- //--------------------------------------------------------------------------------
- // TDBRecord::Verify
- //--------------------------------------------------------------------------------
- void TDBRecord::Verify(TTransaction* t, Boolean verifyDeep /* = false */) const
- {
- if( (this->RecordIndex() == this->ParentSiblingIndex(t)) ||
- (this->RecordIndex() == this->LeftSiblingIndex(t)) ||
- (this->RecordIndex() == this->RightSiblingIndex(t)) )
- DebugStr("\ppTDBRecord::Verify record points at itself!");
-
- //
- // First check out the parent sibling link
- //
- AConst<TDBRecord> parent = this->LiteralParentSibling(t);
- if(parent.Exists())
- {
- if(parent->IdentifyChild(t, AConst<TDBRecord>(this)) == kNodeIsNotAChild)
- DebugStr("\pTDBRecord::Verify parent doesn't point back");
- }
-
- //
- // Next check left and right siblings
- //
- AConst<TDBRecord> left = this->LeftSibling(t);
- if(left.Exists())
- {
- if(left->LiteralParentSibling(t)->RecordIndex() != this->RecordIndex())
- DebugStr("\pTDBRecord::Verify left sibling doesn't point back");
- }
- AConst<TDBRecord> right = this->RightSibling(t);
- if(right.Exists())
- {
- if(right->LiteralParentSibling(t)->RecordIndex() != this->RecordIndex())
- DebugStr("\pTDBRecord::Verify right sibling doesn't point back");
- }
-
- //
- // In deep verifies, we recursively verify the left and right
- // children, and we also test the tree order of this nodes
- // predecessor and successor, and check out the node's balance factor.
- //
- if(verifyDeep)
- {
- if(left.Exists())
- left->Verify(t, verifyDeep);
- if(right.Exists())
- right->Verify(t, verifyDeep);
-
- #if 0
- //
- // Test the ordering of the elements in the tree
- // (note: elements are sometimes temporarily mis-ordered,
- // then are put back into order, hense the #if 0)
- //
- AConst<TDBRecord> predecessor = this->PreviousItemInTree(t);
- if(predecessor.Exists())
- {
- if(this->CompareTreeOrder(t, predecessor) != kSecondObjectComesBefore)
- DebugStr("\pRecord should go before its predecessor!");
- }
- AConst<TDBRecord> successor = this->NextItemInTree(t);
- if(successor.Exists())
- {
- if(this->CompareTreeOrder(t, successor) != kSecondObjectComesAfter)
- DebugStr("\pRecord should come after its successor!");
- }
- #endif
-
- //
- // Finally, test the recorded balance factor against reality
- //
- long leftDepth = 0;
- if(left.Exists())
- leftDepth = 1 + left->DeepestSubtree(t);
- long rightDepth = 0;
- if(right.Exists())
- rightDepth = 1 + right->DeepestSubtree(t);
- if((rightDepth - leftDepth > 1) || (rightDepth - leftDepth < -1))
- DebugStr("\ppTDBRecord::Verify tree balance factor greater than one");
- else switch(this->BalanceFactor(t))
- {
- case kSubtreesBalanced:
- if(rightDepth != leftDepth)
- DebugStr("\pSubtree marked balanced when it isn't");
- break;
- case kLeftSideHigher:
- if(rightDepth >= leftDepth)
- DebugStr("\pSubtree marked left-heavy when it isn't");
- break;
- case kRightSideHigher:
- if(rightDepth <= leftDepth)
- DebugStr("\pSubtree marked right-heavy when it isn't");
- break;
- default:
- DebugStr("\pBalance factor set to unknown value");
- }
- }
- } // TDBRecord::Verify
-
- //--------------------------------------------------------------------------------
- // TDBRecord::TopOfTree
- //--------------------------------------------------------------------------------
- AConst<TDBRecord> TDBRecord::TopOfTree(TTransaction* t) const
- {
- AConst<TDBRecord> treeTop = AConst<TDBRecord>(this);
-
- while((treeTop->RecordIsInATree(t)) && (treeTop->RecordIsAtTopOfTree(t) == false))
- treeTop = treeTop->LiteralParentSibling(t);
-
- Require(treeTop.Exists());
-
- return treeTop;
- } // TDBRecord::TopOfTree
-
- //--------------------------------------------------------------------------------
- // TDBRecord::TreeOwner
- //--------------------------------------------------------------------------------
- AConst<TDBRecord> TDBRecord::TreeOwner(TTransaction* t) const
- {
- AConst<TDBRecord> treeTop = this->TopOfTree(t);
- AConst<TDBRecord> owner(nil);
-
- if(treeTop.Exists())
- {
- owner = treeTop->LiteralParentSibling(t);
- }
-
- return owner;
- } // TDBRecord::TreeOwner
-
- //--------------------------------------------------------------------------------
- // TDBRecord::GoUpUntil
- //--------------------------------------------------------------------------------
- AConst<TDBRecord> TDBRecord::GoUpUntil(TTransaction* t, ChildIdentifier fromDirection) const
- {
- AConst<TDBRecord> cameFrom = AConst<TDBRecord>(this);
- AConst<TDBRecord> upTo = cameFrom->ParentSibling(t);
-
- while((upTo.Exists()) && (upTo->IdentifyChild(t, cameFrom) != fromDirection))
- {
- cameFrom = upTo;
- upTo = cameFrom->ParentSibling(t);
- }
-
- return upTo;
- } // TDBRecord::GoUpUntil
-
- //--------------------------------------------------------------------------------
- // TDBRecord::FirstItemInTree
- //--------------------------------------------------------------------------------
- AConst<TDBRecord> TDBRecord::FirstItemInTree(TTransaction* t) const
- {
- AConst<TDBRecord> topOfTree = this->TopOfTree(t);
- AConst<TDBRecord> firstItemInTree = topOfTree->FirstItemInSubTree(t);
-
- return firstItemInTree;
- } // TDBRecord::FirstItemInTree
-
- //--------------------------------------------------------------------------------
- // TDBRecord::LastItemInTree
- //--------------------------------------------------------------------------------
- AConst<TDBRecord> TDBRecord::LastItemInTree(TTransaction* t) const
- {
- AConst<TDBRecord> topOfTree = this->TopOfTree(t);
- AConst<TDBRecord> lastItemInTree = topOfTree->LastItemInSubTree(t);
-
- return lastItemInTree;
- } // TDBRecord::LastItemInTree
-
- //--------------------------------------------------------------------------------
- // TDBRecord::FindItemInTree
- //--------------------------------------------------------------------------------
- AConst<TDBRecord> TDBRecord::FindItemInTree(TTransaction* t, TAbstractDBComparisonObject* doCompare) const
- {
- AConst<TDBRecord> topOfTree = this->TopOfTree(t);
- AConst<TDBRecord> foundItem = topOfTree->FindItemInSubTree(t, doCompare);
-
- return foundItem;
- } // TDBRecord::FindItemInTree
-
- //--------------------------------------------------------------------------------
- // TDBRecord::NumberOfChildSiblings
- //--------------------------------------------------------------------------------
- long TDBRecord::NumberOfChildSiblings(TTransaction* t) const
- {
- long childSiblings = 0;
-
- AConst<TDBRecord> left = this->LeftSibling(t);
- AConst<TDBRecord> right = this->RightSibling(t);
-
- if(left.Exists())
- childSiblings += left->NumberOfChildSiblings(t) + 1;
- if(right.Exists())
- childSiblings += right->NumberOfChildSiblings(t) + 1;
-
- return childSiblings;
- }
-
- //--------------------------------------------------------------------------------
- // TDBRecord::FirstItemInSubTree
- //--------------------------------------------------------------------------------
- AConst<TDBRecord> TDBRecord::FirstItemInSubTree(TTransaction* t) const
- {
- AConst<TDBRecord> firstItem = AConst<TDBRecord>(this);
-
- while(firstItem->HasLeftSibling(t))
- {
- firstItem = firstItem->LeftSibling(t);
- }
- return firstItem;
- } // TDBRecord::FirstItemInSubTree
-
- //--------------------------------------------------------------------------------
- // TDBRecord::LastItemInSubTree
- //--------------------------------------------------------------------------------
- AConst<TDBRecord> TDBRecord::LastItemInSubTree(TTransaction* t) const
- {
- AConst<TDBRecord> lastItem = AConst<TDBRecord>(this);
-
- while(lastItem->HasRightSibling(t))
- {
- lastItem = lastItem->RightSibling(t);
- }
- return lastItem;
- } // TDBRecord::LastItemInSubTree
-
- //--------------------------------------------------------------------------------
- // TDBRecord::NextItemInTree
- //--------------------------------------------------------------------------------
- AConst<TDBRecord> TDBRecord::NextItemInTree(TTransaction* t) const
- {
- AConst<TDBRecord> nextItem = this->RightSibling(t);
-
- //
- // If there is a node in our RightSibling slot, then
- // the next node in the tree can be found by going down
- // one step to the right, and then following the left
- // links all the way to the end.
- //
- if(nextItem.Exists())
- {
- nextItem = nextItem->FirstItemInSubTree(t);
- }
- //
- // If there isn't an entry in our RightSibling slot,
- // then the next node in the tree is somewhere above
- // us (or we've come to the end of the tree and should
- // return nil--one or the other).
- //
- else
- {
- nextItem = this->GoUpUntil(t, kNodeIsLeftChild);
- }
-
- return nextItem;
- } // TDBRecord::NextItemInTree
-
- //--------------------------------------------------------------------------------
- // TDBRecord::PreviousItemInTree
- //--------------------------------------------------------------------------------
- AConst<TDBRecord> TDBRecord::PreviousItemInTree(TTransaction* t) const
- {
- AConst<TDBRecord> previousItem = this->LeftSibling(t);
-
- //
- // If there is a node in our LeftSibling slot, then
- // the previous node in the tree can be found by going down
- // one step to the left, and then following the right
- // links all the way to the end.
- //
- if(previousItem.Exists())
- {
- previousItem = previousItem->LastItemInSubTree(t);
- }
- //
- // If there isn't an entry in our LeftSibling slot,
- // then the previous node in the tree is somewhere above
- // us (or we've come to the beginning of the tree and should
- // return nil--one or the other).
- //
- else
- {
- previousItem = this->GoUpUntil(t, kNodeIsRightChild);
- }
-
- return previousItem;
- } // TDBRecord::PreviousItemInTree
-
- //--------------------------------------------------------------------------------
- // TDBRecord::FindItemInSubTree
- //--------------------------------------------------------------------------------
- AConst<TDBRecord> TDBRecord::FindItemInSubTree(TTransaction* t, TAbstractDBComparisonObject* doCompare) const
- {
- REQUIREVALIDPOINTER(doCompare);
-
- AConst<TDBRecord> testRecord = AConst<TDBRecord>(this);
-
- while(testRecord.Exists())
- {
- CompareEnumeration theTest = doCompare->TestObject(t, testRecord);
- if(theTest != kObjectKeysEqual)
- {
- //
- // If the second object (the object being examined)
- // comes after the search key, then we'll find the
- // search key somewhere down the left side of the tree
- // (which is where the smaller items are found)
- //
- if(theTest == kSecondObjectComesAfter)
- testRecord = testRecord->LeftSibling(t);
- else if(theTest == kSecondObjectComesBefore)
- testRecord = testRecord->RightSibling(t);
- }
- else
- break;
- }
-
- return testRecord;
- } // TDBRecord::FindItemInSubTree
-
- //--------------------------------------------------------------------------------
- // TDBRecord::Insert
- //--------------------------------------------------------------------------------
- Boolean TDBRecord::Insert(TTransaction* t, AnUpdate<TDBRecord> insertThis)
- {
- Boolean treeGrewTaller = false;
-
- Require(insertThis->RecordIsInATree(t) == false);
- Require((insertThis->HasRightSibling(t) == false) && (insertThis->HasLeftSibling(t) == false));
-
- //
- // Case 1: Insert to the right
- //
- if(this->CompareTreeOrder(t, insertThis) == kSecondObjectComesAfter)
- {
- //
- // We want to insert the node to the right; if there's nothing
- // to the right, then we can just fill in the empty slot
- //
- if(this->HasRightSibling(t) == false)
- {
- ASSERT(this->BalanceFactor(t) != kRightSideHigher);
-
- insertThis->SetRecordIsAtTopOfTree(t, false);
- insertThis->SetParentSibling(t, this);
- insertThis->SetBalanceFactor(t, kSubtreesBalanced);
- this->SetRightSibling(t, insertThis);
-
- //
- // The right subtree was empty; now it has one node.
- //
- treeGrewTaller = true;
- }
- //
- // If there's already something to the right, then
- // we need to make a recursive call to insert
- //
- else
- {
- AConst<TDBRecord> rightChild = this->RightSibling(t);
- treeGrewTaller = (this->Transaction()->GetDBRecordUpdatePointer(rightChild))->Insert(t, insertThis);
- }
-
- //
- // At this point we know that we inserted a node
- // somewhere on the right branch. 'treeGrewTaller'
- // is true if the right subtree grew taller, false
- // if it stayed the same height. The node was balanced
- // before the insert, so if the right subtree did not
- // change in height, then we know that this node is
- // still balanced.
- //
- if(treeGrewTaller)
- {
- switch(this->BalanceFactor(t))
- {
- //
- // If this node was balanced and the right side just
- // grew taller, then mark this node as being right-heavy
- // and note that this subtree has grown taller.
- //
- case kSubtreesBalanced:
- {
- this->SetBalanceFactor(t, kRightSideHigher);
- treeGrewTaller = true;
- break;
- }
- //
- // If the left side of this tree used to be one
- // node taller than the right, and the right subtree
- // just grew taller by one, then mark this node as
- // being balanced and note that this tree did not
- // grow any taller.
- //
- case kLeftSideHigher:
- {
- this->SetBalanceFactor(t, kSubtreesBalanced);
- treeGrewTaller = false;
- break;
- }
-
- //
- // If the right subtree was already taller than
- // the left subtree, and the right side grew again,
- // then we need to do a right-side balance.
- //
- case kRightSideHigher:
- {
- this->RightBalance(t);
- treeGrewTaller = false;
- break;
- }
- }
- }
- #if SLOWDEBUG
- //
- // The tree above us may need to be balanced,
- // but at this point this subtree should verify.
- //
- this->Verify(t, true);
- #endif
- }
- //
- // Case 2: Insert to the left
- //
- else
- {
- if(this->HasLeftSibling(t) == false)
- {
- ASSERT(this->BalanceFactor(t) != kLeftSideHigher);
- insertThis->SetRecordIsAtTopOfTree(t, false);
- insertThis->SetParentSibling(t, this);
- insertThis->SetBalanceFactor(t, kSubtreesBalanced);
- this->SetLeftSibling(t, insertThis);
- treeGrewTaller = true;
- }
- else
- {
- AConst<TDBRecord> leftChild = this->LeftSibling(t);
- treeGrewTaller = (this->Transaction()->GetDBRecordUpdatePointer(leftChild))->Insert(t, insertThis);
- }
- if(treeGrewTaller)
- {
- switch(this->BalanceFactor(t))
- {
- case kSubtreesBalanced:
- {
- this->SetBalanceFactor(t, kLeftSideHigher);
- treeGrewTaller = true;
- break;
- }
- case kRightSideHigher:
- {
- this->SetBalanceFactor(t, kSubtreesBalanced);
- treeGrewTaller = false;
- break;
- }
- case kLeftSideHigher:
- {
- this->LeftBalance(t);
- treeGrewTaller = false;
- break;
- }
- }
- }
- #ifdef SLOWDEBUG
- this->Verify(t, true);
- #endif
- }
-
- return treeGrewTaller;
- } // TDBRecord::Insert
-
-
- //--------------------------------------------------------------------------------
- // TDBRecord::RemoveFromTree
- //--------------------------------------------------------------------------------
- void TDBRecord::RemoveFromTree(TTransaction* t)
- {
- //
- // Don't do anything unless we're part of a tree
- //
- if(this->RecordIsInATree(t))
- {
- #if 0
- //
- // Before we do anything, verify that everything in
- // this tree is valid
- //
- // Note: Sometimes this will cause assertions to
- // fire; for example, if the item is being removed
- // from ResortThisRecord, then verify will report
- // that the tree is not sorted correctly
- //
- AConst<TDBRecord> treeTop = this->TopOfTree(t);
- treeTop->Verify(t, true);
- #endif
-
- //
- // If this node has two children, then we need to swap its
- // position in the tree with its immediate predecessor, found
- // by stepping down to the left once and then walking as far to
- // the right as possible. This changes the order of the tree
- // temporarily (this item and its previous item are now out
- // of order), but once this item is removed all items remaining
- // in the tree will be in the correct order.
- //
- if((this->HasRightSibling(t) == true) && (this->HasLeftSibling(t) == true))
- {
- AConst<TDBRecord> swapNode = this->PreviousItemInTree(t);
- this->SwapTreePositions(t, this->Transaction()->GetDBRecordUpdatePointer(swapNode));
- #ifdef SLOWDEBUG
- this->TopOfTree(t)->Verify(t, true);
- #endif
- }
-
- //
- // Remember our parent node before we put our child into the
- // slot we used to occupy (since we might not have a child, and
- // we don't want to loose our reference to the parent)
- //
- AConst<TDBRecord> balancePoint = this->ParentSibling(t);
-
- //
- // Now that we have zero or one children, move up our
- // child list to the slot that we are vacating.
- // If we don't have any children, then don't bother
- // to do the move.
- //
- AConst<TDBRecord> moveUp(nil);
- if(this->HasLeftSibling(t) == true)
- {
- moveUp = this->LeftSibling(t);
- this->SetLeftSibling(t, nil);
- }
- else if(this->HasRightSibling(t) == true)
- {
- moveUp = this->RightSibling(t);
- this->SetRightSibling(t, nil);
- }
-
- //
- // Make the parent of 'moveUp' be the parent of
- // this node; at this point, 'this' shouldn't have
- // any references inside this tree--it has been
- // completely removed. All that remains to be done
- // is to rebalance the AVL tree.
- //
- // n.b. If 'moveUp' is nil, then SetParentsLinkTothisNodeTo
- // will nil out the parents link to this node
- //
- ChildIdentifier deletedFromSide = this->SetParentsLinkToThisNodeTo(t, moveUp);
- #ifdef SLOWDEBUG
- if(moveUp.Exists())
- {
- moveUp->Verify(t, true);
- }
- #endif
-
- //
- // 'deletedFromSide' will almost always be 'left child' or
- // 'right child'. The only exception is if we just removed
- // the root of the tree, which is only possible in a two-node
- // tree (otherwise the root would have been swapped with
- // some leaf node, and we would be removing a leaf, not the root).
- //
- if((deletedFromSide == kNodeIsLeftChild) || (deletedFromSide == kNodeIsRightChild))
- {
- //
- // Keep fixing up the balancing of the tree until we
- // get a point where the tree is longer on the other
- // branch (the one we didn't delete from); at that
- // point we can mark the tree as balanced and stop
- // adjusting it.
- //
- Boolean treeBecameShorter = true;
- while((balancePoint.Exists()) && (treeBecameShorter == true))
- {
- #ifdef SLOWDEBUG
- //
- // At this point in the execution of Remove, we know that
- // the balance point is unbalanced, but its children should
- // be okay
- //
- AConst<TDBRecord> verifyLeft = balancePoint->LeftSibling(t);
- if(verifyLeft.Exists())
- verifyLeft->Verify(t, true);
- AConst<TDBRecord> verifyRight = balancePoint->RightSibling(t);
- if(verifyRight.Exists())
- verifyRight->Verify(t, true);
- #endif
-
- //
- // We must record which node we're planning on going to
- // next right away, because otherwise a tree rotation
- // could push 'balancePoint' down; if that happens, we
- // want to go up to the balance point's former parent,
- // not its new parent.
- //
- AConst<TDBRecord> nextBalancePoint = balancePoint->ParentSibling(t);
- ChildIdentifier nextDeletedFromSide = kNodeIsNotAChild;
- if(nextBalancePoint.Exists())
- nextDeletedFromSide = nextBalancePoint->IdentifyChild(t, balancePoint);
-
- //
- // Set 'testFactor' to the side we _didn't_ delete
- // from (if the balance point was exactly balanced,
- // we'll set its balance factor to this value)
- //
- long testFactor = ((deletedFromSide == kNodeIsLeftChild) ? kRightSideHigher : kLeftSideHigher);
-
- //
- // Case 1: Removing a node from a balanced subtree.
- // Mark the tree unbalanced, and we're done
- //
- if(balancePoint->BalanceFactor(t) == kSubtreesBalanced)
- {
- (this->Transaction()->GetDBRecordUpdatePointer(balancePoint))->SetBalanceFactor(t, testFactor);
- treeBecameShorter = false;
- }
- //
- // Case 2: Removing a node from the longer side of
- // an unbalanced subtree. Mark the tree balanced,
- // but keep going.
- //
- else if(balancePoint->BalanceFactor(t) != testFactor)
- {
- (this->Transaction()->GetDBRecordUpdatePointer(balancePoint))->SetBalanceFactor(t, kSubtreesBalanced);
- treeBecameShorter = true;
- }
- //
- // Case 3: Removing a node from the shorter side of an
- // unbalanced subtree. Rotations are necessary
- // to bring the tree back into alignment
- //
- else
- {
- AConst<TDBRecord> tallerSubtree = (deletedFromSide == kNodeIsLeftChild) ? balancePoint->RightSibling(t) : balancePoint->LeftSibling(t);
- Require(tallerSubtree.Exists());
-
- //
- // Case 3a: Taller subtree is balanced
- //
- if(tallerSubtree->BalanceFactor(t) == kSubtreesBalanced)
- {
- if(deletedFromSide == kNodeIsLeftChild)
- {
- (this->Transaction()->GetDBRecordUpdatePointer(balancePoint))->SetBalanceFactor(t, kRightSideHigher);
- (this->Transaction()->GetDBRecordUpdatePointer(tallerSubtree))->SetBalanceFactor(t, kLeftSideHigher);
- (this->Transaction()->GetDBRecordUpdatePointer(balancePoint))->RotateLeft(t);
- }
- else
- {
- (this->Transaction()->GetDBRecordUpdatePointer(balancePoint))->SetBalanceFactor(t, kLeftSideHigher);
- (this->Transaction()->GetDBRecordUpdatePointer(tallerSubtree))->SetBalanceFactor(t, kRightSideHigher);
- (this->Transaction()->GetDBRecordUpdatePointer(balancePoint))->RotateRight(t);
- }
- treeBecameShorter = false;
- }
- //
- // Case 3b: Taller subtree has the same balance
- // factor as the balance point
- //
- else if(tallerSubtree->BalanceFactor(t) == balancePoint->BalanceFactor(t))
- {
- (this->Transaction()->GetDBRecordUpdatePointer(balancePoint))->SetBalanceFactor(t, kSubtreesBalanced);
- (this->Transaction()->GetDBRecordUpdatePointer(tallerSubtree))->SetBalanceFactor(t, kSubtreesBalanced);
- if(deletedFromSide == kNodeIsLeftChild)
- (this->Transaction()->GetDBRecordUpdatePointer(balancePoint))->RotateLeft(t);
- else
- (this->Transaction()->GetDBRecordUpdatePointer(balancePoint))->RotateRight(t);
- treeBecameShorter = true;
- }
- //
- // Case 3c: Taller subtree has a different balance
- // factor than the balance point
- //
- else
- {
- if(deletedFromSide == kNodeIsLeftChild)
- (this->Transaction()->GetDBRecordUpdatePointer(balancePoint))->DoubleRotateRightSide(t);
- else
- (this->Transaction()->GetDBRecordUpdatePointer(balancePoint))->DoubleRotateLeftSide(t);
- treeBecameShorter = true;
- }
- }
-
- #ifdef SLOWDEBUG
- //
- // The balance point should now verify; if the balance
- // point was moved down, though, then its parent should
- // also be balanced.
- //
- AConst<TDBRecord> balancePointsNewParent = balancePoint->ParentSibling(t);
- if((balancePointsNewParent.Exists() == false) || (nextBalancePoint.Exists() == false) || (balancePointsNewParent->RecordIndex() == nextBalancePoint->RecordIndex()))
- balancePoint->Verify(t, true);
- else
- balancePointsNewParent->Verify(t, true);
- #endif
-
- //
- // Go up to the next node of the tree. Stop if we
- // hit the top, or if treeBecameShorter is set to false
- //
- balancePoint = nextBalancePoint;
- deletedFromSide = nextDeletedFromSide;
- }
- }
-
- //
- // Finally, nil out our parent-sibling link, since we're
- // not part of any tree any longer. Make sure that we
- // really don't have any left or right child references,
- // and set the bits that indicate that this node is at
- // the top of a tree, and it's subtrees are balanced (which
- // is what an unattached childless node should look like)
- //
- this->SetParentSibling(t, nil);
- if((this->HasRightSibling(t) == true) || (this->HasLeftSibling(t) == true))
- DebugStr("\pOh oh, child sibling links still exist in TDBRecord::RemoveFromTree");
- this->SetRecordIsAtTopOfTree(t, true);
- this->SetBalanceFactor(t, kSubtreesBalanced);
- }
- } // TDBRecord::RemoveFromTree
-
- //--------------------------------------------------------------------------------
- // TDBRecord::ResortThisRecord
- //
- // The method "ResortThisRecord" should be called whenever the sort key
- // for this record changes; doing that removes and re-inserts this record
- // in the tree it is currently contained in.
- //--------------------------------------------------------------------------------
- void TDBRecord::ResortThisRecord(TTransaction* t)
- {
- //
- // Hang onto a reference to some other element in
- // the same tree that we're in
- //
- AConst<TDBRecord> someOtherRecord = this->ParentSibling(t);
- if(someOtherRecord.Exists() == false)
- someOtherRecord = this->LeftSibling(t);
- if(someOtherRecord.Exists() == false)
- someOtherRecord = this->RightSibling(t);
-
- //
- // If this is the only record in the tree, then we
- // don't need to resort.
- //
- // Note: It might be worthwhile to look at the
- // previous and next items in the tree, and only
- // do a resort if this item really does need to
- // move away from its current location.
- //
- if(someOtherRecord.Exists())
- {
- //
- // Remove this entry from the tree, then find the new top-of-tree record
- //
- this->RemoveFromTree(t);
- AConst<TDBRecord> topOfTree = someOtherRecord->TopOfTree(t);
- #ifdef SLOWDEBUG
- this->Verify(t);
- topOfTree->Verify(t, true);
- #endif
-
- //
- // Reinsert this element back into the tree.
- //
- (this->Transaction()->GetDBRecordUpdatePointer(topOfTree))->Insert(t, this);
- #ifdef SLOWDEBUG
- this->Verify(t);
- this->TopOfTree(t)->Verify(t, true);
- #endif
- }
- } // TDBRecord::ResortThisRecord
-
- //--------------------------------------------------------------------------------
- // TDBRecord::RightBalance
- //
- // Assumptions: A node was just inserted on the right side of this tree, and
- // it made the subtree grow taller. There was already at least one node on
- // the right side before the insertion.
- //--------------------------------------------------------------------------------
- void TDBRecord::RightBalance(TTransaction* t)
- {
- AConst<TDBRecord> rootOfRightSubtree = this->RightSibling(t);
- Require(rootOfRightSubtree.Exists());
-
- switch(rootOfRightSubtree->BalanceFactor(t))
- {
- case kRightSideHigher:
- {
- //
- // Do a left rotation
- //
- (this->Transaction()->GetDBRecordUpdatePointer(rootOfRightSubtree))->SetBalanceFactor(t, kSubtreesBalanced);
- this->SetBalanceFactor(t, kSubtreesBalanced);
- this->RotateLeft(t);
- break;
- }
-
- case kLeftSideHigher:
- {
- this->DoubleRotateRightSide(t);
- break;
- }
-
- case kSubtreesBalanced:
- {
- //
- // This should never happen
- //
- Require(false);
- this->Verify(t, true);
- break;
- }
- }
- } // TDBRecord::RightBalance
-
- //--------------------------------------------------------------------------------
- // TDBRecord::LeftBalance
- //
- // Assumptions: A node was just inserted on the left side of this tree, and
- // it made the subtree grow taller. There was already at least one node on
- // the left side before the insertion.
- //--------------------------------------------------------------------------------
- void TDBRecord::LeftBalance(TTransaction* t)
- {
- AConst<TDBRecord> rootOfLeftSubtree = this->LeftSibling(t);
-
- switch(rootOfLeftSubtree->BalanceFactor(t))
- {
- case kLeftSideHigher:
- {
- //
- // Do a right rotation
- //
- (this->Transaction()->GetDBRecordUpdatePointer(rootOfLeftSubtree))->SetBalanceFactor(t, kSubtreesBalanced);
- this->SetBalanceFactor(t, kSubtreesBalanced);
- this->RotateRight(t);
- break;
- }
-
- case kRightSideHigher:
- {
- this->DoubleRotateLeftSide(t);
- break;
- }
-
- case kSubtreesBalanced:
- {
- //
- // This should never happen
- //
- Require(false);
- this->Verify(t, true);
- break;
- }
- }
- } // TDBRecord::LeftBalance
-
- //--------------------------------------------------------------------------------
- // TDBRecord::RotateLeft
- //--------------------------------------------------------------------------------
- void TDBRecord::RotateLeft(TTransaction* t)
- {
- AConst<TDBRecord> rootOfRightSubtree = this->RightSibling(t);
- if(rootOfRightSubtree.Exists())
- {
- AConst<TDBRecord> leftChildOfRightSubtree = rootOfRightSubtree->LeftSibling(t);
-
- this->SetRightSibling(t, leftChildOfRightSubtree);
- if(leftChildOfRightSubtree.Exists())
- {
- (this->Transaction()->GetDBRecordUpdatePointer(leftChildOfRightSubtree))->SetParentSibling(t, this);
- }
- this->SetParentsLinkToThisNodeTo(t, rootOfRightSubtree);
- (this->Transaction()->GetDBRecordUpdatePointer(rootOfRightSubtree))->SetLeftSibling(t, this);
- this->SetParentSibling(t, rootOfRightSubtree);
- }
- } // TDBRecord::RotateLeft
-
- //--------------------------------------------------------------------------------
- // TDBRecord::RotateRight
- //--------------------------------------------------------------------------------
- void TDBRecord::RotateRight(TTransaction* t)
- {
- AConst<TDBRecord> rootOfLeftSubtree = this->LeftSibling(t);
- if(rootOfLeftSubtree.Exists())
- {
- AConst<TDBRecord> rightChildOfRightSubtree = rootOfLeftSubtree->RightSibling(t);
-
- this->SetLeftSibling(t, rightChildOfRightSubtree);
- if(rightChildOfRightSubtree.Exists())
- {
- (this->Transaction()->GetDBRecordUpdatePointer(rightChildOfRightSubtree))->SetParentSibling(t, this);
- }
- this->SetParentsLinkToThisNodeTo(t, rootOfLeftSubtree);
- (this->Transaction()->GetDBRecordUpdatePointer(rootOfLeftSubtree))->SetRightSibling(t, this);
- this->SetParentSibling(t, rootOfLeftSubtree);
- }
- } // TDBRecord::RotateLeft
-
- //--------------------------------------------------------------------------------
- // TDBRecord::DoubleRotateRightSide
- //--------------------------------------------------------------------------------
- void TDBRecord::DoubleRotateRightSide(TTransaction* t)
- {
- AConst<TDBRecord> rootOfRightSubtree = this->RightSibling(t);
- Require(rootOfRightSubtree.Exists());
- AConst<TDBRecord> leftSiblingOfRootOfRight = rootOfRightSubtree->LeftSibling(t);
- Require(leftSiblingOfRootOfRight.Exists());
-
- switch(leftSiblingOfRootOfRight->BalanceFactor(t))
- {
- case kSubtreesBalanced:
- {
- this->SetBalanceFactor(t, kSubtreesBalanced);
- (this->Transaction()->GetDBRecordUpdatePointer(rootOfRightSubtree))->SetBalanceFactor(t, kSubtreesBalanced);
- break;
- }
-
- case kLeftSideHigher:
- {
- this->SetBalanceFactor(t, kSubtreesBalanced);
- (this->Transaction()->GetDBRecordUpdatePointer(rootOfRightSubtree))->SetBalanceFactor(t, kRightSideHigher);
- break;
- }
-
- case kRightSideHigher:
- {
- this->SetBalanceFactor(t, kLeftSideHigher);
- (this->Transaction()->GetDBRecordUpdatePointer(rootOfRightSubtree))->SetBalanceFactor(t, kSubtreesBalanced);
- break;
- }
- }
- (this->Transaction()->GetDBRecordUpdatePointer(leftSiblingOfRootOfRight))->SetBalanceFactor(t, kSubtreesBalanced);
- (this->Transaction()->GetDBRecordUpdatePointer(rootOfRightSubtree))->RotateRight(t);
- this->RotateLeft(t);
- } // TDBRecord::DoubleRotateRightSide
-
- //--------------------------------------------------------------------------------
- // TDBRecord::DoubleRotateLeftSide
- //--------------------------------------------------------------------------------
- void TDBRecord::DoubleRotateLeftSide(TTransaction* t)
- {
- AConst<TDBRecord> rootOfLeftSubtree = this->LeftSibling(t);
- Require(rootOfLeftSubtree.Exists());
- AConst<TDBRecord> rightSiblingOfRootOfLeft = rootOfLeftSubtree->RightSibling(t);
- Require(rightSiblingOfRootOfLeft.Exists());
-
- switch(rightSiblingOfRootOfLeft->BalanceFactor(t))
- {
- case kSubtreesBalanced:
- {
- this->SetBalanceFactor(t, kSubtreesBalanced);
- (this->Transaction()->GetDBRecordUpdatePointer(rootOfLeftSubtree))->SetBalanceFactor(t, kSubtreesBalanced);
- break;
- }
-
- case kRightSideHigher:
- {
- this->SetBalanceFactor(t, kSubtreesBalanced);
- (this->Transaction()->GetDBRecordUpdatePointer(rootOfLeftSubtree))->SetBalanceFactor(t, kLeftSideHigher);
- break;
- }
-
- case kLeftSideHigher:
- {
- this->SetBalanceFactor(t, kRightSideHigher);
- (this->Transaction()->GetDBRecordUpdatePointer(rootOfLeftSubtree))->SetBalanceFactor(t, kSubtreesBalanced);
- break;
- }
- }
- (this->Transaction()->GetDBRecordUpdatePointer(rightSiblingOfRootOfLeft))->SetBalanceFactor(t, kSubtreesBalanced);
-
- (this->Transaction()->GetDBRecordUpdatePointer(rootOfLeftSubtree))->RotateLeft(t);
- this->RotateRight(t);
- } // TDBRecord::DoubleRotateLeftSide
-
- //--------------------------------------------------------------------------------
- // TDBRecord::InitializeNewRecord
- //--------------------------------------------------------------------------------
- void TDBRecord::InitializeNewRecord(TTransaction* t)
- {
- Require(this->ThisRecordIsFree(t));
-
- this->SetParentSiblingIndex(t, kNilIndex);
- this->SetLeftSiblingIndex(t, kNilIndex);
- this->SetRightSiblingIndex(t, kNilIndex);
- } // TDBRecord::InitializeNewRecord
-
- //--------------------------------------------------------------------------------
- // TDBRecord::PropertyValueChanged
- //
- // Whenever a property changes value, it informs the record that owns it by
- // calling this method.
- //--------------------------------------------------------------------------------
- void TDBRecord::PropertyValueChanged(TTransaction*, AConst<TDBProperty> /*propertyThatChanged*/)
- {
- } // TDBRecord::PropertyValueChanged
-
- //--------------------------------------------------------------------------------
- // TDBRecord::RecordCanHaveElements
- //
- // This method must return 'true' if the record can contain elements.
- //--------------------------------------------------------------------------------
- Boolean TDBRecord::RecordCanHaveElements(TTransaction*) const
- {
- return false;
- } // TDBRecord::RecordCanHaveElements
-
- //--------------------------------------------------------------------------------
- // TDBRecord::RecordCanHaveProperties
- //
- // This method must return 'true' if the record can contain properties.
- //--------------------------------------------------------------------------------
- Boolean TDBRecord::RecordCanHaveProperties(TTransaction*) const
- {
- return false;
- } // TDBRecord::RecordCanHaveProperties
-
- //--------------------------------------------------------------------------------
- // TDBRecord::RequireRecordCanHaveElements
- //
- // This method will fail if the record cannot contain elements, or do nothing
- // if it can.
- //--------------------------------------------------------------------------------
- void TDBRecord::RequireRecordCanHaveElements(TTransaction* t) const
- {
- if(this->RecordCanHaveElements(t) == false)
- FailErr(eWrongDataType);
- } // TDBRecord::RequireRecordCanHaveElements
-
- //--------------------------------------------------------------------------------
- // TDBRecord::RequireRecordCanHaveProperties
- //
- // This method will fail if the record cannot contain properties, or do nothing
- // if it can.
- //--------------------------------------------------------------------------------
- void TDBRecord::RequireRecordCanHaveProperties(TTransaction* t) const
- {
- if(this->RecordCanHaveProperties(t) == false)
- FailErr(eWrongDataType);
- } // TDBRecord::RequireRecordCanHaveProperties
-
- //--------------------------------------------------------------------------------
- // TDBRecord::SetChildLinkOfNewParent
- //--------------------------------------------------------------------------------
- void TDBRecord::SetChildLinkOfNewParent(TTransaction* t, AConst<TDBRecord> newChild, ChildIdentifier whichChild)
- {
- Boolean isAtTop = false;
-
- switch(whichChild)
- {
- case kNodeIsLeftChild:
- this->SetLeftSibling(t, newChild);
- break;
-
- case kNodeIsRightChild:
- this->SetRightSibling(t, newChild);
- break;
-
- case kNodeIsTopOfElementTree:
- isAtTop = true;
- this->SetElements(t, newChild);
- break;
-
- case kNodeIsTopOfPropertyTree:
- isAtTop = true;
- this->SetProperties(t, newChild);
- break;
-
- default:
- Throw(eLinksCorrupt);
- }
-
- //
- // It is possible that someone may want to set the child
- // link of the new parent to 'nil', in which case we won't
- // need to point the new child back to its new parent.
- //
- if(newChild.Exists())
- {
- AnUpdate<TDBRecord> newChildUpdate = this->Transaction()->GetDBRecordUpdatePointer(newChild);
- newChildUpdate->SetRecordIsAtTopOfTree(t, isAtTop);
- newChildUpdate->SetParentSibling(t, this);
- }
- } // TDBRecord::SetChildLinkOfNewParent
-
- //--------------------------------------------------------------------------------
- // TDBRecord::SetParentsLinkToThisNodeTo
- //
- // This routine is called when 'newChild' is being rotated into the slot that
- // this record formerly occupied. It is the responsibility of this routine to
- // insure that whichever node previously pointed to this record will
- // thereafter always point to 'newChild' instead.
- //--------------------------------------------------------------------------------
- ChildIdentifier TDBRecord::SetParentsLinkToThisNodeTo(TTransaction* t, AConst<TDBRecord> newChild)
- {
- AConst<TDBRecord> parentSibling = this->LiteralParentSibling(t);
- ChildIdentifier whichChild = kNodeIsNotAChild;
-
- if(parentSibling.Exists())
- {
- whichChild = parentSibling->IdentifyChild(t, this);
- (this->Transaction()->GetDBRecordUpdatePointer(parentSibling))->SetChildLinkOfNewParent(t, newChild, whichChild);
- this->SetParentSibling(t, nil);
- this->SetRecordIsAtTopOfTree(t, false);
- }
-
- return whichChild;
- } // TDBRecord::SetParentsLinkToThisNodeTo
-
- //--------------------------------------------------------------------------------
- // TDBRecord::SwapTreePositions
- //--------------------------------------------------------------------------------
- void TDBRecord::SwapTreePositions(TTransaction* t, AnUpdate<TDBRecord> swapWith)
- {
- //
- // The first step is to look up all of the adjacent
- // links for both nodes before changing anything
- //
- AConst<TDBRecord> thisLeftSibling = this->LeftSibling(t);
- AConst<TDBRecord> thisRightSibling = this->RightSibling(t);
- AConst<TDBRecord> thisParent = this->LiteralParentSibling(t);
- long thisBalanceFactor = this->BalanceFactor(t);
- AConst<TDBRecord> othersLeftSibling = swapWith->LeftSibling(t);
- AConst<TDBRecord> othersRightSibling = swapWith->RightSibling(t);
- AConst<TDBRecord> othersParent = swapWith->LiteralParentSibling(t);
- long otherBalanceFactor = swapWith->BalanceFactor(t);
- ChildIdentifier thisLinkage;
- ChildIdentifier othersLinkage;
- OSErr err = noErr;
-
- //
- // We really expect that this routine will be called on two
- // records that are both part of the same tree, but this is
- // not required; in fact, one of the records may not even
- // be in a tree. The one thing that would be really really
- // bad would be to swap an element with a property; we should
- // test for this, but we currently do not.
- //
- // At any rate, it is very important to remember how the
- // nodes were linked before doing the special-checking for
- // swapping adjacent nodes.
- //
- if(thisParent.Exists())
- thisLinkage = thisParent->IdentifyChild(t, this);
- if(othersParent.Exists())
- othersLinkage = othersParent->IdentifyChild(t, swapWith);
-
- //
- // Next, we need to do special-checking for adjacent records
- // (gasp, hack)
- //
- if(thisLeftSibling.Exists() && (thisLeftSibling->RecordIndex() == swapWith->RecordIndex()))
- {
- Require(othersParent->RecordIndex() == this->RecordIndex());
- thisLeftSibling = this;
- othersParent = swapWith;
- }
- if(thisRightSibling.Exists() && (thisRightSibling->RecordIndex() == swapWith->RecordIndex()))
- {
- Require(othersParent->RecordIndex() == this->RecordIndex());
- thisRightSibling = this;
- othersParent = swapWith;
- }
- if(othersLeftSibling.Exists() && (othersLeftSibling->RecordIndex() == this->RecordIndex()))
- {
- Require(thisParent->RecordIndex() == swapWith->RecordIndex());
- othersLeftSibling = swapWith;
- thisParent = this;
- }
- if(othersRightSibling.Exists() && (othersRightSibling->RecordIndex() == this->RecordIndex()))
- {
- Require(thisParent->RecordIndex() == swapWith->RecordIndex());
- othersRightSibling = swapWith;
- thisParent = this;
- }
-
- Try
- {
- //
- // Relink other node
- //
- swapWith->SetLeftSibling(t, thisLeftSibling);
- swapWith->SetRightSibling(t, thisRightSibling);
- swapWith->SetBalanceFactor(t, thisBalanceFactor);
- if(thisParent.Exists())
- {
- (this->Transaction()->GetDBRecordUpdatePointer(thisParent))->SetChildLinkOfNewParent(t, swapWith, thisLinkage);
- thisParent = nil;
- }
- else
- swapWith->SetParentSibling(t, nil);
- if(thisLeftSibling.Exists())
- {
- (this->Transaction()->GetDBRecordUpdatePointer(thisLeftSibling))->SetParentSibling(t, swapWith);
- thisLeftSibling = nil;
- }
- if(thisRightSibling.Exists())
- {
- (this->Transaction()->GetDBRecordUpdatePointer(thisRightSibling))->SetParentSibling(t, swapWith);
- thisRightSibling = nil;
- }
-
- //
- // Relink this node
- //
- this->SetLeftSibling(t, othersLeftSibling);
- this->SetRightSibling(t, othersRightSibling);
- this->SetBalanceFactor(t, otherBalanceFactor);
- if(othersParent.Exists())
- {
- (this->Transaction()->GetDBRecordUpdatePointer(othersParent))->SetChildLinkOfNewParent(t, AConst<TDBRecord>(this), othersLinkage);
- othersParent = nil;
- }
- else
- this->SetParentSibling(t, nil);
- if(othersLeftSibling.Exists())
- {
- (this->Transaction()->GetDBRecordUpdatePointer(othersLeftSibling))->SetParentSibling(t, this);
- }
- if(othersRightSibling.Exists())
- {
- (this->Transaction()->GetDBRecordUpdatePointer(othersRightSibling))->SetParentSibling(t, this);
- }
- }
- Catch(err)
- {
- Throw(err);
- }
- } // TDBRecord::SwapTreePositions
-
- //================================================================================
- // Class TAbstractRecordIterator
- //================================================================================
-
- //--------------------------------------------------------------------------------
- // TAbstractRecordIterator::TAbstractRecordIterator
- //--------------------------------------------------------------------------------
- TAbstractRecordIterator::TAbstractRecordIterator(TTransaction* transaction, AConst<TDBRecord> cursor, Boolean direction /* = kIterateForward */)
- {
- fCursor = cursor;
- fDirection = direction;
- fTransaction = transaction;
- this->Reset();
- }
-
- //--------------------------------------------------------------------------------
- // TAbstractRecordIterator::Reset
- //--------------------------------------------------------------------------------
- void TAbstractRecordIterator::Reset(Boolean direction /* = kIterateForward */)
- {
- fDirection = direction;
- fHaveRemovedCurrent = false;
- if(fCursor.Exists())
- {
- if(this->IterateForward())
- fCurrent = fCursor->FirstItemInTree(fTransaction);
- else
- fCurrent = fCursor->LastItemInTree(fTransaction);
- }
- else
- fCurrent = nil;
- } // TAbstractRecordIterator::Reset
-
- //--------------------------------------------------------------------------------
- // TAbstractRecordIterator::~TAbstractRecordIterator
- //--------------------------------------------------------------------------------
- TAbstractRecordIterator::~TAbstractRecordIterator()
- {
- if(fCurrent.Exists())
- {
- fCurrent = AConst<TDBRecord>(nil);
- }
- } // TAbstractRecordIterator::~TAbstractRecordIterator
-
- //--------------------------------------------------------------------------------
- // TAbstractRecordIterator::Next
- //--------------------------------------------------------------------------------
- void TAbstractRecordIterator::Next()
- {
- if(fCurrent.Exists() && (fHaveRemovedCurrent == false))
- {
- AConst<TDBRecord> next;
-
- if(this->IterateForward())
- next = fCurrent->NextItemInTree(fTransaction);
- else
- next = fCurrent->PreviousItemInTree(fTransaction);
-
- fCurrent = next;
- }
-
- fHaveRemovedCurrent = false;
- } // TAbstractRecordIterator::Next
-
- //--------------------------------------------------------------------------------
- // TAbstractRecordIterator::RemoveCurrent
- //--------------------------------------------------------------------------------
- void TAbstractRecordIterator::RemoveCurrent()
- {
- fHaveRemovedCurrent = false;
- AConst<TDBRecord> recordToRemove = fCurrent;
- if(recordToRemove.Exists())
- {
- this->Next();
- (fTransaction->GetDBRecordUpdatePointer(recordToRemove))->RemoveFromTree(fTransaction);
- fHaveRemovedCurrent = true;
- }
- } // TAbstractRecordIterator::RemoveCurrent
-